package org.wlw.sort;

public class TestSort {
	public static void main(String[] args) {
		int[] arr = {12,3,1,41,41,23,4,2,51,51,24,2};
//		selectSort(arr);
//		bubbleSort(arr);
		insertSort(arr);
		printArr(arr);
	}
	
	public static void printArr(int[] arr) {
		for(int i=0;i<arr.length;i++) {
			System.out.print(arr[i]+",");
		}
		System.out.println("\n================================");
	}
	
	public static void swap(int[] arr,int i,int j) {
		int c = arr[i];
		arr[i] = arr[j];
		arr[j] = c;
	}
	
	public static void insertSort(int[] arr) {
		for(int i=0;i<arr.length-1;i++) {
			for(int j=i+1;j>0;j--) {
				if(arr[j]<arr[j-1]) {
					swap(arr,j,j-1);
				}
			}
		}
	}
	//冒泡排序交换次数多余选择排序，但是是稳定的
	public static void bubbleSort(int[] arr) {
		for(int i=arr.length-1;i>=0;i--) {
			for(int j=0;j<i;j++) {
				if(arr[j]>arr[j+1]) {
					swap(arr,j,j+1);
				}
			}
		}
	}
	
	//选择排序，交换次数最少，不稳定
	public static void selectSort(int []arr) {
		for(int i=0;i<arr.length;i++) {
			int k = i;
			for(int j=i+1;j<arr.length;j++) {
				if(arr[j]<arr[k]) {
					k = j;
				}
			}
			if(k!=i) {
				swap(arr,k,i);
			}
		}
	}
}
